package com.yc.algorithm.leetcode.btree;

/**
 * Title:<br>
 * Description: <br>
 * Author:陈圆(chenyuan@bosssoft.com.cn) <br>
 * Date:2020/9/1
 */
public class BTNode<K extends Comparable<K>, V> {
    // 构成B树的最小度数
    public final static int MIN_DEGREE = 3;
    // 除根节点外，每个节点中总键数的下限
    public final static int LOWER_BOUND_KEYNUM = MIN_DEGREE - 1;
    // 包含根节点外，每个结点中总键数的上限
    public final static int UPPER_BOUND_KEYNUM = (MIN_DEGREE * 2) - 1;

    protected boolean mIsLeaf; // 标记此节点是否为叶子节点
    protected int mCurrentKeyNum; // 此节点关键字数量
    protected BTKeyValue<K, V>[] mKeys; // 用于存键值对的数组 就是关键字
    protected BTNode<K, V>[] mChildren; // 用于存子结点的数组

    /**
     * 节点的构造方法
     */
    @SuppressWarnings({"unchecked", "unused"})
    public BTNode() {
        this.mIsLeaf = true;
        this.mCurrentKeyNum = 0;
        this.mKeys = new BTKeyValue[UPPER_BOUND_KEYNUM];
        this.mChildren = new BTNode[UPPER_BOUND_KEYNUM + 1];
    }

    protected static BTNode<?, ?> getChildNodeAtIndex(
            BTNode<?, ?> btNode, int keyIdx, int nDirection) {
        if (btNode.mIsLeaf) {
            return null;
        }
        keyIdx += nDirection;
        if ((keyIdx < 0) || (keyIdx > btNode.mCurrentKeyNum)) {
            throw new IllegalArgumentException();
        }
        return btNode.mChildren[keyIdx];
    }
}
